# source:https://leetcode.cn/problems/design-memory-allocator/ 模拟
class Allocator:

    def __init__(self, n: int):
        self.store = [0]*n
        self.n = n
    def allocate(self, size: int, mID: int) -> int:
        i = 0
        while i < self.n:
            cnt = 0
            while i < self.n and self.store[i] == 0 and cnt < size:
                cnt += 1
                i += 1
            if cnt == size:
                for ind in range(i-cnt, i):
                    self.store[ind] = mID
                break
            i += 1
        else:
            return -1
        return i - cnt


    def freeMemory(self, mID: int) -> int:
        ans = 0
        for i in range(self.n):
            if self.store[i] == mID:
                self.store[i] = 0
                ans += 1
        return ans


# Your Allocator object will be instantiated and called as such:
# obj = Allocator(n)
# param_1 = obj.allocate(size,mID)
# param_2 = obj.freeMemory(mID)

# source:https://leetcode.cn/problems/minimum-difficulty-of-a-job-schedule/ 划分型DP 记忆化搜索
from functools import cache
from math import inf
from typing import List
class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        @cache
        def dfs(i, cnt):
            if cnt == 0:
                if i < 0:
                    return 0
                return inf
            if i < 0:
                return inf
            res = inf
            for j in range(i+1):
                res = min(res, dfs(j-1, cnt-1)+f[j][i])
            return res
        
        n = len(jobDifficulty)
        f = [[0]*n for _ in range(n)]
        for length in range(n):
            for i in range(n-length):
                j = i + length
                if i == j:
                    f[i][j] = jobDifficulty[i]
                else:
                    f[i][j] = max(f[i][j-1], jobDifficulty[j])
        return dfs(n-1, d) if dfs(n-1, d) != inf else -1
    
# source:https://leetcode.cn/problems/maximum-non-negative-product-in-a-matrix/ 状态机DP 记忆化搜索
class Solution:
    def maxProductPath(self, nums: List[List[int]]) -> int:
        @cache
        def dfs(i, j):
            if i == 0 and j == 0:
                return nums[i][j], nums[i][j]
            res1, res2 = -inf, inf
            if i > 0:
                res1 = max(dfs(i-1, j)[0]*nums[i][j], dfs(i-1, j)[1]*nums[i][j], res1)
                res2 = min(dfs(i-1, j)[1]*nums[i][j], dfs(i-1, j)[0]*nums[i][j], res2)
            if j > 0:
                res1 = max(dfs(i, j-1)[0]*nums[i][j], dfs(i, j-1)[1]*nums[i][j], res1)
                res2 = min(dfs(i, j-1)[1]*nums[i][j], dfs(i, j-1)[0]*nums[i][j], res2)
            return res1, res2
        n, m = len(nums), len(nums[0])
        return dfs(n-1, m-1)[0] % (pow(10, 9)+7) if dfs(n-1, m-1)[0] >= 0 else -1

# source:https://leetcode.cn/problems/visit-array-positions-to-maximize-score/ 状态机DP 记忆化搜索
class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int) -> int:
            if i == len(nums):
                return 0
            if nums[i] % 2 != j:
                return dfs(i + 1, j)
            return max(dfs(i + 1, j), dfs(i + 1, j ^ 1) - x) + nums[i]
        return dfs(0, nums[0] % 2)